package sort.mergesort;

import java.util.Arrays;

/**
 * @author XY
 * @version 1.0
 * @date 2021/9/9 16:31
 * @Description
 */
public class ReversePairs {

    public int res= 0;

    public int reversePairs(int[] nums) {
        int[] temp= Arrays.copyOf(nums,nums.length);
        sort(nums,0,nums.length-1,temp);
        return res;
    }

    private void sort(int[] arr,int l,int r,int[] temp){
        if(l>=r){
            return ;
        }
        int mid = l+(r-l)/2;
        sort(arr, l, mid,temp);
        sort(arr,mid+1,r,temp);
        if(arr[mid]>arr[mid+1]){
            merge2(arr,l,mid,r,temp);
        }
    }

    private void merge2(int[] arr,int l,int mid,int r,int[] temp){
        System.arraycopy(arr,l,temp, l ,r-l+1);
        int i=l;
        int j=mid+1;
        for (int n=l;n<=r;n++) {
            if(i>mid){
                arr[n]=temp[j];
                j++;
            }else if(j>r){
                arr[n]=temp[i];
                i++;
            }else if (temp[i]<=temp[j]){
                //l代表偏移量
                arr[n]=temp[i];
                i++;
            }else{
                //每次递归右边比当前元素小的数都是逆序数对
                res+=(mid-i+1);
                arr[n]=temp[j];
                j++;
            }
        }
    }
}
